package structure;
import java.util.*;

public class Test7 {
    public static void main(String[] args) {
        Scanner in = new Scanner(System.in);

    }
    //leetcode75.颜色分类
    class Solution {
        public void sortColors(int[] nums) {
            int l = 0;
            int r = nums.length - 1;
            quickSort(nums, l, r);
        }
        public void quickSort(int[] nums,int start,int end){
            //递归出口
            if(start >= end){
                return;
            }
            int base = nums[start];
            int left = start;
            int right = end;
            while(left < right){
                //从右往左找 "比base小的值" (若 nums[right] >= base 则继续找)
                while(left < right && nums[right] >= base){
                    right--;
                }
                //找到目标值,将 nums[left] 替换成 nums[right] (意在将小于 base 的值放在左边)
                nums[left] = nums[right];
                //从左往右找 "比base大的值" (若 nums[left] <= base 则继续找)
                while(left < right && nums[left] <= base){
                    left++;
                }
                //找到目标值,将 nums[right] 替换成 nums[left] (意在将大于 base 的值放在右边)
                nums[right] = nums[left];
            }
            //此时 left = right 将中间值base放入该处,代表该处左边都小于base,该处右边都大于base
            nums[left] = base;
            //递归左半部分数组再次排序
            quickSort(nums,start,left - 1);
            //递归右半部分数组再次排序
            quickSort(nums,left + 1,end);
        }
    }
    //leetcode11.盛最多水的容器
    class Solution0 {
        public int maxArea(int[] height) {
            int l = 0;
            int r = height.length - 1;
            int num = 0;
            while(l < r){
                int n = Math.min(height[r],height[l]) * (r - l);
                if(n > num){
                    num = n;
                }
                //右边大于左边,代表此时已是"存在该左边"情况下的最大面积
                //所以不再需要该左边,l++;
                if(height[r] > height[l]){
                    l++;
                }else {//与上同理
                    r--;
                }
            }
            return num;
        }
    }
    //蓝桥杯 左移右移(⭐⭐⭐)
    public static void main1(String[] args) {
        Scanner in = new Scanner(System.in);
        //在此输入您的代码...
        int N = in.nextInt();
        int M = in.nextInt();
        int[] l = new int[N + 5];
        int[] r = new int[N + 5];
        //第一个结点从 1 开始
        for(int i = 1;i <= N;i++){
            l[i] = i - 1;
            r[i] = i + 1;
        }
        //创建右边缘,即 n + 1
        l[N + 1] = N;
        //创建左边缘,即 0
        r[0] = 1;
        //后续对结点的"头插"和"尾插"
        //都只用"左边缘0"和"右边缘N+1"
        while(M-- > 0){
            char c = in.next().charAt(0);
            int num = in.nextInt();
            r[l[num]] = r[num];
            l[r[num]] = l[num];
            if(c == 'L'){
                //r[0]代表左边缘的下一位,也就是第一个结点
                //l[r[0]]代表l[1], = num 代表 num变成第一个结点
                l[r[0]] = num;
                //num的上一位设为左边缘
                l[num] = 0;
                r[num] = r[0];
                r[0] = num;
            }else {
                r[l[N+1]] = num;
                l[num] = l[N+1];
                r[num] = N+1;
                l[N+1] = num;
            }
        }
        for(int i = r[0];i != N + 1;i = r[i]){
            System.out.print(i + " ");
        }
        in.close();
    }
}
